import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.println("before: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("after: " + Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr) {
        int len = arr.length;
        mergeSortCore(arr, 0, len - 1);
    }

    public static void mergeSortCore(int[] arr, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l >> 1);
        mergeSortCore(arr, l, mid);
        mergeSortCore(arr, mid + 1, r);
        merge(arr, l, r, mid);
    }

    public static void merge(int[] arr, int l, int r, int mid) {
        int[] res = new int[r - l + 1];
        int p1 = l, p2 = mid + 1, p = 0;
        while (p1 <= mid && p2 <= r) {
            res[p++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid){
            res[p++] = arr[p1++];
        }
        while (p2 <= r) {
            res[p++] = arr[p2++];
        }
        System.arraycopy(res, 0, arr, l, r - l + 1);
    }

}
